#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s = "283164705";
string goal = "123804765";

int x, y, nodeNum, queueord;
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
struct node
{
	int f, step;
	string now;
	string last;
	int loc, childNum = 0;
	string isPath;
	bool operator<(const node &x) const { return f > x.f; }
};

priority_queue<node> q;
map<string, node> fpath;
map<string, bool> mp;
map<string, int> dis;
const int n = 1024;
string Fourtree[n];

void output_impl(int num, int left, string const &indent)
{
	if (Fourtree[num] == "" || num > n)
		return;
	for (int i = 1; i <= 2; i++)
	{
		if (Fourtree[4 * num + i] == "" || 4 * num + i > n)
			break;
		output_impl(4 * num + i, i, indent + (left == 2 || left == 3 ? "|     " : "      "));
	}
	cout << indent << (left <= 2 ? '/' : '\\') << "-----";
	cout << Fourtree[num].substr(0, Fourtree[num].length() - 9) << endl;
	for (int i = 3; i <= 4; i++)
	{
		if (Fourtree[4 * num + i] == "" || 4 * num + i > n)
			break;
		output_impl(4 * num + i, i, indent + (left == 2 || left == 3 ? "|     " : "      "));
	}
}

void draw()
{
	puts("A directed graph of state space:");
	puts("PS: * means the step of  A-star algorithm \n");
	for (int i = 1; i <= 4; i++)
	{
		if (i <= 2)
			output_impl(i, true, "|");
		else
		{
			if (i == 3)
				cout << Fourtree[0].substr(0, 3) << "*" << endl;

			output_impl(i, i, "|");
		}
	}
}
void print(string cur)
{
	for (int i = 0; i < 3; i++)
	{
		putchar('\t');
		for (int j = 0; j < 3; j++)
		{
			printf("%c ", cur[3 * i + j] == '0' ? ' ' : cur[3 * i + j]);
		}
		puts("");
	}
	return;
}
void outPath()
{
	// 建图 数组
	// 生成对应顺序表四叉树
	for (map<string, node>::iterator iter = fpath.begin(); iter != fpath.end(); ++iter)
	{
		node node = iter->second;
		Fourtree[node.loc] = node.isPath != "" ? "  *" + node.isPath + node.now : node.now;
		// Fourtree[node.loc] = node.isPath? node.isPath+"*"+node.now:node.now;
		nodeNum++;
	}
	// 解释
	puts("PS:\n");
	for (int i = 0, ord = 0; ord < nodeNum; i++)
		if (Fourtree[i] != "")
		{
			printf("S_%d is\n", ord);
			print(Fourtree[i].substr(Fourtree[i].length() - 9, Fourtree[i].length()));
			putchar('\n');
			char sn[100];
			sprintf(sn, "S_%d", ord++);
			Fourtree[i] = sn + Fourtree[i];
		}
	// 画图
	draw();
}

int h(string cur)
{
	int res = 0;
	for (int i = 0; i < 9; i++)
		if (goal[i] != cur[i] && goal[i] != 0)
			res++;
	return res;
}

int h2(string cur)
{
	int res = 0;
	for (int i = 0; i < 9; i++)
		if (goal[i] != cur[i] && goal[i] != 0)
			res++;
	return res;
}

// void mark_Path(string cur){
// 	map<string,node>::iterator iter = fpath.find(cur);
// 	node now =iter->second;
// 	if(now.last!="") now.isPath = true;
// 	else mark_Path(now.last);
// 	return;
// }
void A_STAR()
{
	while (!q.empty())
	{
		node t = q.top();
		q.pop();
		string cur = t.now;

		// print(cur);
		map<string, node>::iterator iter = fpath.find(cur);
		char qo[255];
		sprintf(qo, "%d", queueord++);
		iter->second.isPath = qo;
		if (cur == "123804765")
		{
			// mark_Path(cur);
			return;
		}
		// else puts("  ↓");
		int sx, sy;
		for (int i = 0; i < 9; i++)
			if (cur[i] - '0' == 0)
				sx = i / 3 + 1, sy = i % 3 + 1;
		int tmp1 = (sx - 1) * 3 + sy - 1;
		for (int i = 0; i < 4; i++)
		{
			int xx = dx[i] + sx, yy = dy[i] + sy;
			if (xx < 1 || xx > 3 || yy < 1 || yy > 3)
				continue;
			int tmp2 = (xx - 1) * 3 + yy - 1;
			string last = cur;
			swap(cur[tmp1], cur[tmp2]);
			if (mp[cur] == 0 || (mp[cur] == 1 && (t.step + 1) < dis[cur]))
			{
				dis[cur] = t.step + 1;
				t.childNum++;
				fpath[cur] = (node){h(cur) + t.step + 1, t.step + 1, cur, last, 4 * t.loc + t.childNum};
				q.push(fpath[cur]);
				mp[cur] = 1;
			}
			swap(cur[tmp1], cur[tmp2]);
		}
	}
}

int main()
{
	if (h(s) == 0){puts("0");return 0;}
	while (q.size())
		q.pop();
	fpath[s] = (node){h(s), 0, s, "", 0};
	q.push(fpath[s]);
	mp[s] = 1;
	dis[s] = 0;
	A_STAR();
	outPath();
	return 0;
}